1. Field of the Invention
This invention relates in general to a method and apparatus for handling packets, and more particularly to a method and apparatus for providing multi-protocol, multi-stage, real-time frame classification.
2. Description of Related Art
Standards-based LAN systems work reasonably well at transfer rates up to about 100 Mbps. At transfer rates above 100 Mbps, providing the processing power required by a packet switch interconnecting a group of networks becomes economically challenging for the performance levels desired. This difficulty in economically “scaling up” performance is beginning to cause restrictions in some user's planned network expansions. Also, today's data networks do not provide network managers with enough control over bandwidth allocation and user access.
Next generation networks are expected to support “multimedia” applications with their much greater bandwidth and real-time delivery requirements. The next generation networks should also have the ability to dynamically adjust the network so that it can guarantee a predetermined amount of bandwidth for the requested service level agreement. Additionally, it is desirable to provide access, performance, fault tolerance and security between any specified set of end systems as directed by the network's manager.
One of the biggest opportunities for service providers today is to provide IP-based internetworking services to meet the exponential growth in demand from both business and residential customers. For example, voice and video based multimedia applications are expected to become a significant portion of the Internet. However, support for multimedia applications in the current Internet is at its initial stages. To fulfill the promise of remote work styles and B2C (Business-to-Consumer) e-commerce, broadband access for small offices, home offices and residences is critical. In today's information-based society, many individuals desire remote data connectivity to an office or remote data site. Remote individuals desire remote and transparent connectivity to the corporate office or a remote data site, including connectivity to the corporate office local area network (LAN).
Broadband systems are being developed and implemented to provide higher capacities, more efficient use of bandwidth, and the ability to integrate voice, data, and video communications. The number and type of communication services has also been rapidly expanding, including the above-mentioned “multimedia” services such as video teleconferencing, video/movies on demand and the like.
While broadband access is becoming more common, there are many competing technologies for delivering broadband access. For example, there are a number of standards used in digital telecommunications, including TCP/IP, Ethernet, HDLC, ISDN, ATM, X.25, Frame Relay, Digital Data Service, FDDI (Fiber Distributed Data Interface), T1, xDSL, Wireless, Cable Modems, and Satellite among others. Many of these standards employ different packet and/or frame formats. The term “frame” generally refers to encapsulated data at OSI layer 2, including a destination address, control bits for flow control, the data or payload, and CRC (cyclic redundancy check) data for error checking. The term “packet” generally refers to encapsulated data at OSI layer 3. However, in the present application, the term packet and frame and cell will be used interchangeably.
In general, a packet format or frame format refers to how data is encapsulated with various fields and headers for transmission across a network. For example, a data packet typically includes an address destination field, a length field, an error correcting code (ECC) field or cyclic redundancy check (CRC) field, as well as headers and trailers to identify the beginning and end of the packet. The terms “packet format” and “frame format”, also referred to as “cell format”, are generally synonymous.
In order for a router or gateway to be able to interface between communication systems employing different packet or frame formats, the node element, such as the router or gateway, is required to perform a packet conversion to convert the data from a first packet format used by the first communication system to a second packet format used by the second communication system. As the number of possible packet formats or types increases, the amount of logic required to convert between these different packet formats also increases.
Furthermore, the emergence of high speed networking technologies, e.g., ATM cell-based technology, xDSL, cable modem technology and Gigabit Ethernet, makes possible the integration of multiple types of traffic like speech, video and data over the same communication network. The communication circuits which may be shared in such network include transmission lines, program controlled processors, nodes or links, and data or packet buffers. An access node in such network should thus be designed for supporting the access of the user existing communication equipment with their corresponding protocols as well as for accommodating new equipment. Accordingly, it is essential to know the different requirements of each traffic in order to optimize the different processes.
Real-time traffic has more constraining requirements than non-real-time ones, i.e., end-to-end delay and jitter. It is necessary to be able to give priority to the real-time packets in order to minimize these delays. Meanwhile, the packet loss must be guaranteed both for real-time and non-real-time applications that have reserved bandwidth in the network while it is not mandatory for non-reserved type of traffic.
Therefore, it is important to provide the network components (i.e. nodes or links) with mechanisms that control the priority of the packets and process them so that the desired quality of service (QOS) to their corresponding connections is guaranteed. It is also important to offer the same service to connections having the same QOS requirements by providing them with a fair share of the network transmission capacities.
As can be seen, the technological convergence of computer and communication networks has led to more complex transmission of data, voice, images etc. Depending on the network, various protocols are hierarchically ordered, resulting in a vertical stack of protocols. Each of these protocols interact with the adjacent ones to organize the information exchange and transmission between remote systems, such as host computers. If an application program, for example, which runs on a first system requires the use of data of a second system, an exchange of information takes place. When the second system receives a request to send specific information, this information has to be transmitted from the highest protocol level, e.g., the application layer, down through all lower protocol levels prior to being sent along the physical link. Each protocol layer adds its own layer-specific connection information to data packets containing the request information that are received from the higher layer.
Thus, a communication connection between two systems is defined in a packet header, hereinafter referred to as protocol header, by the aggregate of fields carrying connection information of the vertical protocol stack. Nevertheless, when receiving a data stream made up of data packets at a receiver site, prior to forwarding, routing, multiplexing or compressing the data packets, the protocol header has to be scanned to extract information to at least identify the connection information.
A fundamental function in processing packets in networking communications is filtering. Filtering is the process of applying a set of rules to an incoming packet in order to determine its forwarding characteristics. Advanced frame identification and/or marking may be used to identify the entire frame composition layer by layer. The rules that are applied to perform the filtering can vary. For example, plural criteria may be used in a given table lookup. Another example uses the results of a one table lookup with certain packet protocol criteria to generate subsequent table lookups. Current methods used to obtain this type of filtering are implemented in software and thereby do not scale with the bandwidth in today's networks. Furthermore, these operations consume a considerable amount of time in the protocol processing, in particular when dealing with many connections, e.g., in a server, or when processing multimedia data streams. The result of this is cumbersome and conventional filtering applied to the high-speed networks leads to network degradation.
Hardware implementation of a routing table for the translation of packet identifiers into an appropriate physical output link has been described in “Putting Routing Tables in Silicon”, T. -B. Pei and C. Zukowski, IEEE Network Magazine, January 1992, pp. 42-50. This approach is mainly characterized in that a Content Addressable Memory (CAM) is employed to match connection information in the header of a single protocol. In addition, the advantages and disadvantages of CAMs versus conventional Random Access Memories (RAM), used to store routing information, have been evaluated by Pei and Zukowski.
In addition to the above-mentioned problems, another problem associated with using a CAM to match connection information in the header. To make filtering decisions, a CAM table is built. The CAM table contains search words. The table may contain fields for the IP source, the type of service, the TCP source port, etc. However, as search words are built, the amount of memory required explodes exponentially.
Neither of the two systems above, both of them relating to the solution of sub-problems, nor the known software approaches allow fast processing of multiple protocols. A wide variety of communication protocols exist, but all tend to fall into one of the following groups: LAN protocols, WAN protocols, network protocols, and routing protocols. LAN protocols operate at the network and data link layers of the OSI model and define communication over the various LAN media. WAN protocols operate at the lowest three layers of the OSI model and define communication over the various wide-area media. Routing protocols are network-layer protocols that are responsible for path determination and traffic switching. Finally, network protocols are the various upper-layer protocols that exist in a given protocol suite. The processing of protocol headers and the recognition of different protocol types in real time is a very complicated and difficult undertaking. In almost all network systems, header processing is still a major CPU-cycle (Central Processor Unit) consuming activity.
It can be seen that there is a need for a method and apparatus for providing multi-protocol, multi-stage, real-time frame classification.